还没有笔记
选中页面文字后点击「高亮」按钮添加
| 课次 | 日期 | 主题 | Sipser 阅读材料 |
|---|---|---|---|
| 1 | 1/21 | 课程概述，自动机简介，语言 | Ch 0, 1.1 |
| 2 | 1/26 | 确定性有限自动机，定义，示例 | Ch 1.1 |
| 3 | 1/28 | 非确定性有限自动机，示例 | Ch 1.2 |
| 4 | 2/2 | NFA，子集构造法 | Ch 1.2 |
| 5 | 2/4 | 正则表达式，定义，示例；转换为 NFA | Ch 1.3 |
| 6 | 2/9 | NFA 转换为正则表达；正则表达式的性质；泵引理 | Ch 1.3, 1.4 |
| 7 | 2/11 | 非正则性：泵引理；封闭性质；Myhill-Nerode 定理 | Ch 1.4 |
| 8 | 2/16 | 上下文无关文法，定义，示例 | Ch 2.1 |
| 9 | 2/18 | 更多关于 CFG 的内容，歧义文法 | Ch 2.1 |
| 10 | 2/23 | 下推自动机；定义，示例 | Ch 2.2 |
| 11 | 2/25 | PDA 和 CFG 的等价性；确定性 PDA | Ch 2.2 |
| 12 | 3/2 | 泵引理；CFL 的封闭性质 | Ch 2.3 |
| 13 | 3/4 | 乔姆斯基范式；CFG 算法 | Ch 2, Thm 7.16 |
| 14 | 3/9 | 图灵机简介 | Ch 3.1 |
| 15 | 3/11 | 图灵机，编程技巧 | Ch 3.1 |
| 16 | 3/23 | 图灵机的扩展和变体 | Ch 3.2 |
| 3/25 | 测验 1（期中）随堂 | ||
| 17 | 3/30 | 可识别语言，可判定语言，通用图灵机 | Ch 3.3, 4.1 |
| 18 | 4/1 | 不可判定性，对角化，停机问题 | Ch 4.2 |
| 19 | 4/6 | 归约，其他不可判定问题；赖斯定理 | Ch 5.1, 5.3 |
| 20 | 4/8 | 更多归约；波斯特对应问题 | Ch 5.2 |
| 21 | 4/13 | 复杂性类，P 类，NP 类，coNP 类 | Ch 7.1, 7.2, 7.3 |
| 22 | 4/15 | NP 示例；归约 | Ch 7.3, 7.4 |
| 23 | 4/20 | NP 完全性，可满足性 | Ch 7.4 |
| 24 | 4/22 | 其他 NP 完全问题 | Ch 7.5 |
| 25 | 4/27 | 其他主题（其他类，随机化） | |
| 26 | 4/29 | 赶进度；复习 | |
| 27 | 5/4 | 测验 2（期末）随堂 |
| Lecture | Date | Topics | Readings in Sipser |
|---|---|---|---|
| 1 | 1/21 | Course overview, Introduction to automata, languages | Ch 0, 1.1 |
| 2 | 1/26 | Deterministic Finite Automata, definitions, examples | Ch 1.1 |
| 3 | 1/28 | Nondeterministic Finite Automata, examples | Ch 1.2 |
| 4 | 2/2 | NFA, Subset construction | Ch 1.2 |
| 5 | 2/4 | Regular expressions, definitions, examples; Conversion to NFA | Ch 1.3 |
| 6 | 2/9 | Conversion from NFA to Reg Exp; Properties of Reg Exp; Pumping lemma | Ch 1.3, 1.4 |
| 7 | 2/11 | Nonregularity: Pumping lemma; closure properties; Myhill-Nerode theorem | Ch 1.4 |
| 8 | 2/16 | Context-free grammars, definitions, examples | Ch 2.1 |
| 9 | 2/18 | More on CFGs, ambiguous grammars | Ch 2.1 |
| 10 | 2/23 | Pushdown automata; definitions, examples | Ch 2.2 |
| 11 | 2/25 | Equivalence of PDA and CFG; Deterministic PDA | Ch 2.2 |
| 12 | 3/2 | Pumping lemma; Closure properties of CFLs | Ch 2.3 |
| 13 | 3/4 | Chomsky normal form; Algorithms for CFGs | Ch 2, Thm 7.16 |
| 14 | 3/9 | Introduction to Turing machines | Ch 3.1 |
| 15 | 3/11 | Turing machines, programming tricks | Ch 3.1 |
| 16 | 3/23 | Extensions, variants of TMs | Ch 3.2 |
| 3/25 | Test 1 (Midterm) in class | ||
| 17 | 3/30 | Recognizable, Decidable languages, Universal TM | Ch 3.3, 4.1 |
| 18 | 4/1 | Undecidability, Diagonalization, Halting problem | Ch 4.2 |
| 19 | 4/6 | Reductions, Other undecidable problems; Rice's theorem | Ch 5.1, 5.3 |
| 20 | 4/8 | More reductions; Post Correspondence problem | Ch 5.2 |
| 21 | 4/13 | Complexity classes, the classes P, NP, coNP | Ch 7.1, 7.2, 7.3 |
| 22 | 4/15 | NP examples; Reductions | Ch 7.3, 7.4 |
| 23 | 4/20 | NP-completeness, Satisfiability | Ch 7.4 |
| 24 | 4/22 | Other NP-complete problems | Ch 7.5 |
| 25 | 4/27 | Other topics (Other classes, Randomization) | |
| 26 | 4/29 | Catchup; Review | |
| 27 | 5/4 | Test 2 (Final) in class |